﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace LisaCore
{
    /// <summary>
    /// This is a basic linked list implementation of the PriorityQueue.
    /// </summary>
    /// <typeparam name="T"></typeparam>
    public class PriorityQueueImpl<T>:IPriorityQueue<T>
    {
        ListNode<T> first;  //The next item to be dequeued (the front of the queue)
        ListNode<T> last;   //The last item to be dequeued (the end of the queue)
        int count;  //the number of elements currently in the queue
        int capacity;   //The maximum number of items that can be stored in the queue

        public PriorityQueueImpl(int capacity)
        {
            first = null;
            last = null;
            count = 0;
            this.capacity = capacity;
        }

        /// <summary>
        /// Enqueues an object with the given priority in the priority queue.
        /// 
        /// </summary>
        /// <param name="item">The item to be enqueued.</param>
        /// <param name="priority">The priority of the item.</param>
        public void Enqueue(T item, int priority)
        {
            lock (this)
            {
                if (isFull()) //Queue is full
                {
                    if (getLowestPriority() < priority) //New item is more important than least important item already in queue
                    {
                        //Remove the item with the lowest priority and enqueue the new item
                        removeItemWithLowestPriority();
                        enqueueHelper(item, priority);
                    }
                }
                else //Queue is not full
                {
                    enqueueHelper(item, priority);
                }
            }
        }

        /// <summary>
        /// Returns and removes the element at the front of the queue.
        /// </summary>
        /// <returns>The element at the front of the queue.</returns>
        public T Dequeue()
        {
            lock (this)
            {
                if (first != null)
                {
                    count--;
                    if (first == last)
                    {
                        T value = first.Value;
                        first = last = first.Previous;
                        return value;
                    }
                    else
                    {
                        T value = first.Value;
                        first = first.Previous;
                        first.Next = null;
                        return value;
                    }
                }
                else
                {
                    return default(T);
                }
            }
        }

        /// <summary>
        /// Returns the highest priority in the queue.
        /// </summary>
        /// <returns>The highest priority in the priority queue.</returns>
        public int getHighestPriority()
        {
            if (first != null)
            {
                return first.Priority;
            }
            else
            {
                return 0;
            }
        }

        /// <summary>
        /// Returns the number of elements in the queue.
        /// </summary>
        /// <returns>The number of elements in the queue.</returns>
        public int size()
        {
            return count;
        }

        /// <summary>
        /// Returns true if the queue is empty.
        /// </summary>
        /// <returns>True if the queue is empty.</returns>
        public bool isEmpty()
        {
            return count == 0;
        }

        /// <summary>
        /// Clears the queue.
        /// </summary>
        public void clear()
        {
            first = last = null;
        }

        #region Private helper methods
        /// <summary>
        /// Enqueues the new item with the given priority in the appropriate part of the priority queue.
        /// </summary>
        /// <param name="item">The new item to be inserted.</param>
        /// <param name="priority">The priority of the item to be inserted.</param>
        void enqueueHelper(T item, int priority)
        {
            if (first == null && last == null) //queue is empty
            {
                first = last = new ListNode<T>(item, priority);
            }
            else if (first != null && last != null) //Queue is not empty
            {
                ListNode<T> newNode = new ListNode<T>(item, priority);
                ListNode<T> currentNode = last;
                while (currentNode.Priority < newNode.Priority && currentNode.Next != null)
                {
                    currentNode = currentNode.Next;
                }
                if (currentNode.Next == null)
                {
                    if (currentNode.Priority < newNode.Priority) //insert at the very front of the queue
                    {
                        currentNode.Next = newNode;
                        newNode.Previous = currentNode;
                        first = newNode;
                    }
                    else
                    {
                        if (currentNode.Previous == null) //insert at the very end of the queue
                        {
                            currentNode.Previous = newNode;
                            newNode.Next = currentNode;
                            last = newNode;
                        }
                        else
                        {
                            currentNode.Previous.Next = newNode;
                            newNode.Previous = currentNode.Previous;
                            newNode.Next = currentNode;
                            currentNode.Previous = newNode;
                        }
                    }
                }
                else
                {
                    if (currentNode.Previous == null) //insert at the very end of the queue
                    {
                        currentNode.Previous = newNode;
                        newNode.Next = currentNode;
                        last = newNode;
                    }
                    else
                    {
                        currentNode.Previous.Next = newNode;
                        newNode.Previous = currentNode.Previous;
                        newNode.Next = currentNode;
                        currentNode.Previous = newNode;
                    }
                }
            }
            count++;
        }

        /// <summary>
        /// Removes the item with the lowest priority from the priority queue.
        /// </summary>
        void removeItemWithLowestPriority()
        {
            if (last != null)
            {
                if (last == first)
                {
                    first = first.Next;
                }
                last = last.Next;
                if (last != null)
                {
                    last.Previous = null;
                }
                count--;
            }
        }

        /// <summary>
        /// Returns the lowest priority in the queue.
        /// </summary>
        /// <returns>The lowest priority in the queue.</returns>
        int getLowestPriority()
        {
            if (last != null)
            {
                return last.Priority;
            }
            else
            {
                return 0;
            }
        }

        /// <summary>
        /// Returns true if the priority queue is full, false otherwise.
        /// </summary>
        /// <returns>True if the priority queue is full, false otherwise.</returns>
        bool isFull()
        {
            return count == capacity;
        }

        #endregion

        /// <summary>
        /// This inner class represents a single ListNode. ListNodes make up a LinkedList. A ListNode contains a field
        /// to hold data, the priority as well as pointers to the next and the previous ListNode in the LinkedList.
        /// </summary>
        /// <typeparam name="E"></typeparam>
        class ListNode<E>
        {
            E value;    //The value stored in the list node

            public E Value
            {
                get { return this.value; }
                set { this.value = value; }
            }
            int priority;   //The priority of the node

            public int Priority
            {
                get { return priority; }
                set { priority = value; }
            }
            ListNode<E> next;   //the pointer to the next node

            public ListNode<E> Next
            {
                get { return next; }
                set { next = value; }
            }
            ListNode<E> previous;   //the pointer to the previous node

            public ListNode<E> Previous
            {
                get { return previous; }
                set { previous = value; }
            }

            public ListNode(E value, int priority)
            {
                this.value = value;
                this.priority = priority;
                next = null;
                previous = null;
            }
        }
    }
}
